package com.nine.algorithm.binarysearch;

import java.util.Arrays;

/**
 * @author nine
 * @version 1.0
 * @description TODO
 * @date 24/4/23 21:53
 */
public class TestBinarySearch {

	public static void main(String[] args) {

		// 二分查找
		// testBinarySearch();

		// java二分查找实现
		// testJavaBinarySearch();


		int[] a = {1, 2, 4, 4, 4, 6, 7, 8, 9};
		int target = 4;
		// leftmost，二分查找含重复元素，返回最左的一个
		int res = BinarySearchLeftmost.binarySearchLeftmost(a, target);
		System.out.println(res);

		int res2 = BinarySearchLeftmost.binarySearchRightmost(a, target);
		System.out.println(res2);

	}

	private static void testJavaBinarySearch() {
		// java的二分查找实现
		int[] a = {1, 3, 5, 7};
		int target = 4;
		int res1 = Arrays.binarySearch(a, target);
		// 返回值为 -3
		// (- 插入点 - 1)，意味着，t1这个数据如果插入到a1中，应该在索引2的位置
		System.out.println(res1);

		if (res1 < 0) {
			// 插入点索引
			int insertIndex = Math.abs(res1 + 1);
			// 新建一个数组，长度为原数组长度+1
			int[] b = new int[a.length + 1];
			// 将a数组在插入点之前的数据拷贝到b数组
			System.arraycopy(a, 0, b, 0, insertIndex);
			System.out.println("==" + Arrays.toString(b));
			b[insertIndex] = target;
			System.out.println("==" + Arrays.toString(b));
			System.arraycopy(a, insertIndex, b, insertIndex + 1, a.length - insertIndex);
			System.out.println("==" + Arrays.toString(b));

		}
	}

	private static void testBinarySearch() {
		int[] a = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
		int target = 11;
		int result = BinarySearch.binarySearchBasicSelf(a, target);
		int result2 = BinarySearch.binarySearchBasic(a, target);
		int result3 = BinarySearch.binarySearchAlternative(a, target);
		int result4 = BinarySearch.binarySearch3(a, target);
		System.out.println(result);
		System.out.println(result2);
		System.out.println(result3);
		System.out.println(result4);
	}

}
